package leetcode_zh

import (
	"math"
	"sort"
)

/**
 * @Description: 1170. 比较字符串最小字母出现频次
 * @Keyword: 二分查找
 * @Author: kami
 * @Date: 2022/5/2 15:33
 **/
func numSmallerByFrequency(queries []string, words []string) []int {
	var qCnt = make([]int, len(queries))
	for i := 0; i < len(queries); i++ {
		var minChar uint8 = 'z'
		var cnt = 0
		for j := 0; j < len(queries[i]); j++ {
			if queries[i][j] < minChar {
				minChar = queries[i][j]
				cnt = 1
			} else if queries[i][j] == minChar {
				cnt++
			}
		}
		qCnt[i] = cnt
	}
	var wCnt = make([]int, len(words))
	for i := 0; i < len(words); i++ {
		var minChar uint8 = 'z'
		var cnt = 0
		for j := 0; j < len(words[i]); j++ {
			if words[i][j] < minChar {
				minChar = words[i][j]
				cnt = 1
			} else if words[i][j] == minChar {
				cnt++
			}
		}
		wCnt[i] = cnt
	}

	sort.Ints(wCnt)
	var res = make([]int, len(queries))
	for i := 0; i < len(queries); i++ {
		res[i] = getCntBiggerThanTargetFromSortArray(wCnt, qCnt[i])
	}
	return res
}

func getCntBiggerThanTargetFromSortArray(source []int, target int) int {
	for i := 0; i < len(source); i++ {
		if source[i] > target {
			return len(source) - i
		}
	}
	return 0
}

/**
 * @Description: 1770. 执行乘法运算的最大分数
 * @Keyword: 遍历
 * @Author: kami
 * @Date: 2022/5/2 16:51
 **/
func maximumScore(nums []int, multipliers []int) int {
	return getMaxScore(nums, 0, len(nums)-1, multipliers, 0, 0)
}

func getMaxScore(nums []int, nStart, nEnd int, multipliers []int, step int, resScore int) (maxScore int) {
	var (
		scoreStart int
		scoreEnd   int
	)

	if step == len(multipliers)-1 {
		scoreStart = multipliers[step] * nums[nStart]
		scoreEnd = multipliers[step] * nums[nEnd]
	} else {
		scoreStart = getMaxScore(nums, nStart+1, nEnd, multipliers, step+1, resScore)
		scoreEnd = getMaxScore(nums, nStart, nEnd-1, multipliers, step+1, resScore)
	}

	if scoreStart > scoreEnd {
		return scoreStart + resScore
	}
	return scoreEnd + resScore
}

/**
 * @Description: 15. 三数之和
 * @Keyword: 双指针
 * @Author: kami
 * @Date: 2022/5/19 15:49
 **/
func threeSum(nums []int) [][]int {
	if len(nums) < 3 {
		return [][]int{}
	}
	sort.Ints(nums)
	if nums[0] > 0 || nums[len(nums)-1] < 0 {
		return [][]int{}
	}
	if nums[0] == 0 && nums[nums[len(nums)-1]] == 0 {
		return [][]int{{0, 0, 0}}
	}
	var res [][]int
	var preVal = math.MinInt
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] == preVal {
			continue
		}
		var left = i + 1
		var right = len(nums) - 1
		for left < right {
			var sum = nums[left] + nums[right]
			if sum == -nums[i] {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				for left < right && nums[left+1] == nums[left] {
					left++
				}
				left++
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				right--
			} else if sum > -nums[i] {
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				right--
			} else {
				for left < right && nums[left+1] == nums[left] {
					left++
				}
				left++
			}
		}

		preVal = nums[i]
	}
	return res
}

/**
 * @Description: 16. 最接近的三数之和
 * @Keyword: 排序+双指针
 * @Author: kami
 * @Date: 2022/5/26 9:12
 **/
func threeSumClosest(nums []int, target int) int {

	sort.Ints(nums)
	var closeTarget = nums[0] + nums[1] + nums[2]
	if closeTarget == target {
		return closeTarget
	}
	var preVal = nums[0] - 1
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] == preVal {
			continue
		}
		var left = i + 1
		var right = len(nums) - 1
		for left < right {
			var sum = nums[i] + nums[left] + nums[right]
			if sum == target {
				return target
			} else if sum > target {
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				right--
			} else {
				for left < right && nums[left+1] == nums[left] {
					left++
				}
				left++
			}
			if abs(sum-target) < abs(closeTarget-target) {
				closeTarget = sum
			}
		}
		preVal = nums[i]
	}
	return closeTarget
}

/**
 * @Description: 46. 全排列
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/5/19 18:44
 **/
func permute(nums []int) [][]int {
	var res [][]int
	var visited = make([]int, len(nums))
	res = backtrack(res, nums, []int{}, visited)
	return res
}

/**
 * @Description: 47. 全排列 II
 * @Keyword: 去除重复，增加判断
 * @Author: kami
 * @Date: 2022/5/25 11:30
 **/
func permuteUnique(nums []int) [][]int {
	var res [][]int
	var visited = make([]int, len(nums))
	sort.Ints(nums)
	res = backtrackUnique(res, nums, []int{}, visited)
	return res
}

func backtrackUnique(res [][]int, nums, temp, visited []int) [][]int {
	if len(temp) == len(nums) {
		var copyTemp = make([]int, len(nums))
		copy(copyTemp, temp)
		res = append(res, copyTemp)
		return res
	}
	for i := 0; i < len(nums); i++ {
		if visited[i] == 1 || (i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) {
			continue
		}
		visited[i] = 1
		temp = append(temp, nums[i])
		res = backtrackUnique(res, nums, temp, visited)
		visited[i] = 0
		temp = temp[:len(temp)-1]
	}

	return res
}

func backtrack(res [][]int, nums, temp, visited []int) [][]int {
	if len(temp) == len(nums) {
		var copyTemp = make([]int, len(nums))
		copy(copyTemp, temp)
		res = append(res, copyTemp)
		return res
	}
	for i := 0; i < len(nums); i++ {
		if visited[i] == 1 {
			continue
		}
		visited[i] = 1
		temp = append(temp, nums[i])
		res = backtrack(res, nums, temp, visited)
		visited[i] = 0
		temp = temp[:len(temp)-1]
	}

	return res
}

/**
 * @Description: 11. 盛最多水的容器
 * @Keyword: 矩形面积
 * @Author: kami
 * @Date: 2022/5/21 16:25
 **/
func maxArea(height []int) int {
	var max int
	var left = 0
	var right = len(height) - 1
	for left < right {
		max = getMax(max, (right-left)*getMin(height[left], height[right]))
		if height[right] > height[left] {
			left++
		} else {
			right--
		}
	}
	return max
}

/**
 * @Description: 17. 电话号码的字母组合
 * @Keyword: 全排列变形
 * @Author: kami
 * @Date: 2022/5/21 16:54
 **/
func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	var digitsLetter = [][]byte{
		{'a', 'b', 'c'},
		{'d', 'e', 'f'},
		{'g', 'h', 'i'},
		{'j', 'k', 'l'},
		{'m', 'n', 'o'},
		{'p', 'q', 'r', 's'},
		{'t', 'u', 'v'},
		{'w', 'x', 'y', 'z'},
	}
	res := backtrackDigits([]string{}, digitsLetter, digits, []byte{}, 0)
	return res
}

func backtrackDigits(res []string, digitsLetter [][]byte, digits string, temp []byte, curIdx int) []string {
	if len(temp) == len(digits) {
		res = append(res, string(temp))
		return res
	}

	var idx = digits[curIdx] - '2'
	for j := 0; j < len(digitsLetter[idx]); j++ {
		temp = append(temp, digitsLetter[idx][j])
		res = backtrackDigits(res, digitsLetter, digits, temp, curIdx+1)
		temp = temp[:len(temp)-1]
	}

	return res
}

/**
 * @Description: 19. 删除链表的倒数第 N 个结点
 * @Keyword: 遍历
 * @Author: kami
 * @Date: 2022/5/21 17:36
 **/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	var size = 0
	var resHead = head
	for head != nil {
		size += 1
		head = head.Next
	}
	if size == n {
		return resHead.Next
	}

	th := size - n
	var pre = resHead
	for i := 1; i < size; i++ {
		var curNode = pre.Next
		if i == th {
			pre.Next = curNode.Next
			return resHead
		}
		pre = curNode
	}
	return resHead
}

/**
 * @Description: 22. 括号生成
 * @Keyword: 回溯法
 * @Author: kami
 * @Date: 2022/5/22 11:01
 **/
func generateParenthesis(n int) []string {
	return backTrackParenthesis([]string{}, []byte{}, n, n)
}

func backTrackParenthesis(res []string, curItem []byte, leftNum, rightNum int) []string {
	if leftNum > rightNum || leftNum < 0 || rightNum < 0 {
		return res
	}
	if leftNum == 0 && rightNum == 0 {
		res = append(res, string(curItem))
		return res
	}
	curItem = append(curItem, '(')
	res = backTrackParenthesis(res, curItem, leftNum-1, rightNum)
	curItem = curItem[:len(curItem)-1]

	curItem = append(curItem, ')')
	res = backTrackParenthesis(res, curItem, leftNum, rightNum-1)
	curItem = curItem[:len(curItem)-1]

	return res
}

/**
 * @Description: 31. 下一个排列
 * @Keyword: 下一个大值的序列
 * @Author: kami
 * @Date: 2022/5/22 11:54
 **/
func nextPermutation(nums []int) {
	if len(nums) <= 1 {
		return
	}

	i, j, k := len(nums)-2, len(nums)-1, len(nums)-1

	// find: A[i]<A[j]
	for i >= 0 && nums[i] >= nums[j] {
		i--
		j--
	}

	if i >= 0 { // 不是最后一个排列
		// find: A[i]<A[k]
		for nums[i] >= nums[k] {
			k--
		}
		// swap A[i], A[k]
		nums[i], nums[k] = nums[k], nums[i]
	}

	// reverse A[j:end]
	for i, j := j, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}

}

/**
 * @Description: 33. 搜索旋转排序数组
 * @Keyword: 二分查找
 * @Author: kami
 * @Date: 2022/5/23 9:11
 **/
func search(nums []int, target int) int {
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		var mid = (left + right) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < nums[right] {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		} else {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {

				left = mid + 1
			}
		}
	}
	return -1
}

/**
 * @Description: 96. 不同的二叉搜索树
 * @Keyword: 卡特兰数 G(n)=G(0)∗G(n−1)+G(1)∗G(n−2)+...+G(n−1)∗G(0)
 * @Author: kami
 * @Date: 2022/5/23 14:31
 **/
func numTrees(n int) int {
	var dp = make([]int, n+1)
	dp[0] = 1
	dp[1] = 1
	for i := 2; i < n+1; i++ {
		for j := 1; j < i+1; j++ {
			dp[i] += dp[j-1] * dp[i-j]
		}
	}
	return dp[n]
}

/**
 * @Description: 34. 在排序数组中查找元素的第一个和最后一个位置
 * @Keyword: 时间复杂度为 logN
 * @Author: kami
 * @Date: 2022/5/23 17:35
 **/
func searchRange(nums []int, target int) []int {
	if len(nums) == 0 || nums[0] > target || nums[len(nums)-1] < target {
		return []int{-1, -1}
	}
	var left = 0
	var right = len(nums) - 1
	var res = []int{-1, -1}
	for left <= right {
		var mid = (left + right) / 2
		if nums[mid] == target {
			var rightA = mid
			// left mid 之间找开始点
			for left <= rightA {
				var tempMid = (left + rightA) / 2
				if nums[tempMid] == target {
					if (tempMid > 0 && nums[tempMid-1] < target) || tempMid == 0 {
						res[0] = tempMid
						break
					}
					rightA = tempMid - 1
				} else if nums[tempMid] > target {
					rightA = tempMid - 1
				} else {
					left = tempMid + 1
				}
			}
			// mid 和right 之间找结束点
			var leftB = mid
			for leftB <= right {
				var tempMid = (leftB + right) / 2
				if nums[tempMid] == target {
					if (tempMid < len(nums)-1 && nums[tempMid+1] > target) || tempMid == len(nums)-1 {
						res[1] = tempMid
						break
					}
					leftB = tempMid + 1
				} else if nums[tempMid] > target {
					right = tempMid - 1
				} else {
					leftB = tempMid + 1
				}
			}
			break
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

/**
 * @Description: 102. 二叉树的层序遍历
 * @Keyword: 使用栈
 * @Author: kami
 * @Date: 2022/5/23 19:32
 **/
func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}

	var curLevelNodes = []*TreeNode{
		root,
	}

	for len(curLevelNodes) > 0 {
		var curSize = len(curLevelNodes)
		var curVals []int
		for i := 0; i < curSize; i++ {
			curVals = append(curVals, curLevelNodes[i].Val)
			if curLevelNodes[i].Left != nil {
				curLevelNodes = append(curLevelNodes, curLevelNodes[i].Left)
			}
			if curLevelNodes[i].Right != nil {
				curLevelNodes = append(curLevelNodes, curLevelNodes[i].Right)
			}
		}
		res = append(res, curVals)
		if len(curLevelNodes) > curSize {
			curLevelNodes = curLevelNodes[curSize:]
		} else {
			break
		}
	}
	return res

}

/**
 * @Description: 107. 二叉树的层序遍历 II
 * @Keyword: 自下而上;队列
 * @Author: kami
 * @Date: 2022/5/27 8:03
 **/
func levelOrderBottom(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}
	var level = []*TreeNode{root}

	for len(level) > 0 {
		n := len(level)
		var nextlevel []*TreeNode
		var curLevel []int
		for i := 0; i < n; i++ {
			curLevel = append(curLevel, level[i].Val)
			if level[i].Left != nil {
				nextlevel = append(nextlevel, level[i].Left)
			}
			if level[i].Right != nil {
				nextlevel = append(nextlevel, level[i].Right)
			}
		}
		res = append([][]int{curLevel}, res...)
		level = nextlevel
	}
	return res
}

/**
 * @Description: 8. 字符串转换整数 (atoi)
 * @Keyword: 这一题不好，题目说明不清晰
 * @Author: kami
 * @Date: 2022/5/25 12:48
 **/
func myAtoi(s string) int {
	// 如果输入的是空字符串，直接返回0
	if s == "" {
		return 0
	}
	i, n := 0, len(s)
	// 忽略前导空格
	for i < n-1 {
		if s[i] == ' ' {
			i++
		} else {
			break
		}
	}
	// 检查非空格的第一位，并获得数字开头的s
	s0 := s[i:]
	if s[i] == '-' || s[i] == '+' {
		s = s[i+1:]
	} else if s[i] >= '0' && s[i] <= '9' {
		s = s[i:]
	} else {
		return 0
	}

	// 遍历s，并转化数字
	// 停止条件为：ch不是数字 或者 num超过最大长度
	num := 0
	for _, ch := range []byte(s) {
		ch -= '0'
		if ch > 9 || ch < 0 {
			break
		}

		num = num*10 + int(ch)
		if num >= 1<<31 {
			num = 1 << 31
			break
		}
	}

	// 有负号的安负号
	if s0[0] == '-' {
		num = -num
	} else {
		// 另一个边界
		if num >= 1<<31-1 {
			num = 1<<31 - 1
		}
	}

	return num
}

/**
 * @Description: 12. 整数转罗马数字 中等
 * @Keyword: 	I             1
				VI			  4
				V             5
				XI            9
				X             10
				LX 			  40
				L             50
				CL            90
				C             100
				DC			  400
				D             500
				MD			  900
				M             1000

 * @Author: kami
 * @Date: 2022/5/26 10:56
 **/
func intToRoman(num int) string {
	var res string
	for num > 0 {
		switch {
		case num/1000 > 0:
			cnt := num / 1000
			res = appendStr(res, "M", cnt)
			num -= 1000 * cnt
		case num/900 == 1:
			res = appendStr(res, "CM", 1)
			num -= 900
		case num/500 == 1:
			res = appendStr(res, "D", 1)
			num -= 500
		case num/400 == 1:
			res = appendStr(res, "CD", 1)
			num -= 400
		case num/100 > 0:
			cnt := num / 100
			res = appendStr(res, "C", cnt)
			num -= 100 * cnt
		case num/90 == 1:
			res = appendStr(res, "XC", 1)
			num -= 90
		case num/50 == 1:
			res = appendStr(res, "L", 1)
			num -= 50
		case num/40 == 1:
			res = appendStr(res, "XL", 1)
			num -= 40
		case num/10 > 0:
			cnt := num / 10
			res = appendStr(res, "X", cnt)
			num -= 10 * cnt
		case num/9 == 1:
			res = appendStr(res, "IX", 1)
			num -= 9
		case num/5 == 1:
			res = appendStr(res, "V", 1)
			num -= 5
		case num/4 == 1:
			res = appendStr(res, "IV", 1)
			num -= 4
		default:
			res = appendStr(res, "I", num)
			num = 0
		}
	}
	return res
}

func appendStr(s string, suffix string, cnt int) string {
	for i := 0; i < cnt; i++ {
		s += suffix
	}
	return s
}

/**
 * @Description: 18. 四数之和 中等
 * @Keyword: 排序+双指针 O（N3）
 * @Author: kami
 * @Date: 2022/5/26 18:23
 **/
func fourSum(nums []int, target int) [][]int {
	var quadruplets [][]int
	sort.Ints(nums)
	n := len(nums)
	for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
		if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target {
			continue
		}
		for j := i + 1; j < n-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
			if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target {
				continue
			}
			for left, right := j+1, n-1; left < right; {
				if sum := nums[i] + nums[j] + nums[left] + nums[right]; sum == target {
					quadruplets = append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]})
					for left++; left < right && nums[left] == nums[left-1]; left++ {
					}
					for right--; left < right && nums[right] == nums[right+1]; right-- {
					}
				} else if sum < target {
					left++
				} else {
					right--
				}
			}
		}
	}
	return quadruplets
}
